package leetcode;

/**
 * @author Liangyaoyun
 */
public class mergeTwoLists {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre=new ListNode(0);
        ListNode cur=pre;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                //将较小的val值存进链表pre
                cur.next=list1;
                //更新list1的节点
                list1=list1.next;
            }else{
                //将较小的val值存进链表pre
                cur.next=list2;
                //更新list2的节点
                list2=list2.next;
            }
            //更新cur链表,创建新的节点
            cur=cur.next;
        }
        //将没放完的节点全部放到cur里
        cur.next=list1!=null?list1:list2;
        return pre.next;
    }
}
